package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.Node;

import java.util.Stack;

/**
 * 非递归遍历树
 *
 * @author Mr_wenpan@163.com 2021/12/22 10:34
 */
public class NotRecursiveTraversal {

    public static void main(String[] args) {

    }

    public static void preOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            System.out.print(pop.data + "   ");
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

    public static void inOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        // 一直把左边界压栈，左边界节点走到空的时候就弹出一个然后将弹出节点的右孩子的左边界一直压栈，任何一棵树都能被左边界分解
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                Node pop = stack.pop();
                System.out.print(pop.data + "   ");
                head = pop.right;
            }
        }
    }

    public static void postOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();

        stack1.push(head);
        while (!stack1.isEmpty()) {
            // 弹出一个，弹出就加入到另一个栈
            Node pop = stack1.pop();
            stack2.push(pop);
            // 先压左再压右
            if (pop.left != null) {
                stack1.push(pop.left);
            }
            if (pop.right != null) {
                stack1.push(pop.right);
            }
        }
        // 将stack2的数据倒出来就是后续
        while (!stack2.isEmpty()) {
            Node pop = stack2.pop();
            System.out.print(pop.data + "   ");
        }
    }
}
